package done.easy_201_300;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最近公共祖先
 * <p>
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
 * 最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度
 * 尽可能大（一个节点也可以是它自己的祖先）。”
 * <p>
 * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
 * <p>
 * 6
 * /    \
 * 2       8
 * /  \     / \
 * 0    4   7   9
 * /  \
 * 3    5
 * <p>
 * 示例 1:
 * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
 * 输出: 6
 * 解释: 节点 2 和节点 8 的最近公共祖先是 6。
 * <p>
 * 2019-03-28 11:09 PM
 **/
@Slf4j
public class LowestCommonAncestorOfABinarySearchTree {

    @SuppressWarnings("all")
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 190328 first
        return null;
    }

    @Test
    public void test() {
        TreeNode p = new TreeNode(7);
        TreeNode q = new TreeNode(0);
        TreeNode root = new TreeNode(6,
                new TreeNode(2,
                        q, new TreeNode(4,
                        3, 5)),
                new TreeNode(8,
                        p, 9));
        log.info("{}", lowestCommonAncestor(root, p, q));
    }
}





























/*
TreeNode res = null;

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    lca(root, p , q);
    return res;
}
private void lca(TreeNode root, TreeNode p , TreeNode q){
    if((root.val - p.val)*(root.val - q.val) <= 0){
        res = root;
    }else if(root.val < p.val && root.val < q.val){
        lca(root.right, p , q);
    }else{
        lca(root.left, p , q);
    }
}
*/
